export type SortItem = {
  gridSize: [number, number];
  i: number;
  [key: string]: any;
};

class Row {
  items: (SortItem | null)[];
  size = 0; // 已经填充的网格大小

  constructor(cols: number) {
    this.items = new Array(cols).fill(null);
  }

  // 放置, 放置成功返回true，失败放回false
  push(item: SortItem) {
    const w = item.gridSize?.[1] ?? 1;
    if (!this.allowPush(w)) return false;

    // 放置
    const findStr = new Array(w).fill("0").join("");
    const index = this.items
      .map((item) => (!item ? "0" : "1"))
      .join("")
      .indexOf(findStr);
    for (let i = index, len = index + findStr.length; i < len; i++) {
      this.items[i] = item;
    }
    this.size += w;

    return true;
  }

  insert(item: SortItem, index: number) {
    for (let i = index, len = index + (item.gridSize?.[1] ?? 1); i < len; i++) {
      this.items[i] = item;
    }
    this.size += item.gridSize?.[1] ?? 1;
  }

  // 是否能放置
  allowPush(w: number) {
    if (this.items.length - this.size < w) return false;

    // 获取最大的连续空间
    const matches = this.items
      .map((item) => (!item ? "0" : "1"))
      .join("")
      .match(/(0)\1*/g); // 获取连续的0
    let maxLength = 0;
    if (matches) {
      matches.forEach((match) => {
        if (match.length > maxLength) {
          maxLength = match.length;
        }
      });
    }

    return maxLength >= w;
  }

  indexOf(item: SortItem) {
    return this.items.indexOf(item);
  }
}

export const gridSorting = (list: SortItem[], cols: number) => {
  // 向一行填充网格, 返回填充行的索引
  const pushToRow = (item: SortItem, container: Row[], cols: number) => {
    // 获取可放置的行
    let row = container.find((row) => row.push(item));
    // 如果没有可放置的行，就新建一行，并添加到容器
    if (!row) {
      row = new Row(cols);
      row.push(item);
      container.push(row);
    }
    return row;
  };

  const container: Row[] = [];

  list.forEach((item) => {
    let currentRow = pushToRow(item, container, cols);
    let h = (item.gridSize?.[0] ?? 1) - 1;

    while (h) {
      const rowIndex = container.indexOf(currentRow); // 添加的行的索引
      const colIndex = container[rowIndex].indexOf(item); // 添加的项在行内的索引
      let nextRow = container[rowIndex + 1];
      if (!container[rowIndex + 1]) {
        nextRow = new Row(cols);
        container.push(nextRow);
      }

      nextRow.insert(item, colIndex);
      currentRow = nextRow;
      h -= 1;
    }
  });

  // 确认最终输出格式
  const arr: Array<
    SortItem & {
      gridArea: string;
      gridPositionBefore?: [number, number];
      index: number;
    }
  > = [];
  container.forEach((row, y) => {
    row.items.forEach((item, x) => {
      if (item && arr.findIndex((it) => item.i === it.i) === -1) {
        const gridSize = item.gridSize ?? [1, 1];
        arr.push({
          ...item,
          gridSize,
          gridPosition: [x + 1, y + 1],
          // gridPositionBefore: item.gridPosition,
          gridArea: `${y + 1}/${x + 1}/span ${gridSize[0]}/span ${gridSize[1]}`,
          i: item.i,
          index: arr.length,
        });
      }
    });
  });

  return arr;
};
